package com.chj.jz.dp.class04;

public class Code07_CombinationSumIv {
	 /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    public static int backPackVI(int[] nums, int target) {
        // write your code here
    	
    	int[] f = new int[target + 1];
    	int i, j;
    	
    	f[0] = 1;
    	for(i = 1; i <= target; i++) {
    		f[i] = 0;
    		for(j = 0; j < nums.length; j++) {
    			if(i >= nums[j]) {
    				f[i] += f[i - nums[j]];
    			}
    		}
    	}
    	
    	return f[target];
    }
    
    public static void main(String[] args) {
		{
			int[] arr = new int[] {1, 2, 4};
			int k = 4;
			System.out.println(backPackVI(arr, k));
		}
		{
			int[] arr = new int[] {1, 2};
			int k = 4;
			System.out.println(backPackVI(arr, k));
		}
    }
}
